package dynamicprogramming;

/**
 * @Author: LDeng
 * @Date: 2021-04-28 9:38
 */
public class Knapsack {
    public static void main(String[] args) {
        int[] values = {6, 3, 5, 4, 6};
        int[] weights = {2, 2, 6, 5, 4};
        int capacity = 10;
        System.out.println("二维数组实现：" + maxValue(values, weights, capacity));
        System.out.println("一维数组实现: " + maxValue1(values, weights, capacity));
        System.out.println("恰好等于背包容量: "+maxValue2(values,weights,capacity));

    }

    //恰好是背包容量
    static int maxValue2(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;
        int n = values.length;//物品总数量
        int[] dp = new int[capacity + 1];
        for(int j=1;j<capacity;j++){
            dp[j]=Integer.MIN_VALUE;//初始化元素为负无穷
        }
        for (int i = 1; i <= n; i++) {
            for (int j = capacity; j >= weights[i-1]; j--) {//循环到weight[i-1]即可， 不用循环到1
                if (j < weights[i - 1]) continue;//背包最大承重小于最后一件物品重量
                //最大承重能容得下最后一件物品
                //最后一件物品不选
                int max1 = dp[j];
                //最后一件物品选中
                int max2 = values[i - 1] + dp[j - weights[i - 1]];
                dp[j] = Math.max(max1, max2);
            }
        }
        return dp[capacity]<0?-1:dp[capacity];
    }


    //一维数组
    static int maxValue1(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;
        int n = values.length;//物品总数量
        int[] dp = new int[capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = capacity; j >= weights[i-1]; j--) {//循环到weight[i-1]即可， 不用循环到1
                if (j < weights[i - 1]) continue;//背包最大承重小于最后一件物品重量
                //最大承重能容得下最后一件物品
                //最后一件物品不选
                int max1 = dp[j];
                //最后一件物品选中
                int max2 = values[i - 1] + dp[j - weights[i - 1]];
                dp[j] = Math.max(max1, max2);
            }
        }
        return dp[capacity];
    }

    //二维数组
    static int maxValue(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;
        int n = values.length;//物品总数量
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {//背包最大承重小于最后一件物品重量
                    dp[i][j] = dp[i - 1][j];
                } else {//最大承重能容得下最后一件物品
                    //最后一件物品不选
                    int max1 = dp[i - 1][j];
                    //最后一件物品选中
                    int max2 = values[i - 1] + dp[i - 1][j - weights[i - 1]];
                    dp[i][j] = Math.max(max1, max2);
                }
            }
        }
        return dp[n][capacity];
    }


}
